package com.ztom.daily.n2022.m6;

/**
 * 删除二叉搜索树中的节点
 * <p>
 * https://leetcode.cn/problems/delete-node-in-a-bst/
 *
 * @author ZhangTao
 */
public class Day02DeleteNode {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key > root.val) {
            // 去右树删, 返回右树的新头
            root.right = deleteNode(root.right, key);
            return root;
        } else if (key < root.val) {
            // 去左树删, 返回左树的新头
            root.left = deleteNode(root.left, key);
            return root;
        } else {
            // 删除当前节点
            if (root.left == null && root.right == null) {
                // 左右子树都为空
                return null;
            }
            // 左空右不空
            if (root.left == null) {
                return root.right;
            }
            // 右空左不空
            if (root.right == null) {
                return root.left;
            }
            // 左右都不空, 新头就是当前节点的后继节点(右子树的最左节点)
            TreeNode node = root.right;
            while (node.left != null) {
                node = node.left;
            }
            deleteNode(root.right, node.val);
            node.right = root.right;
            node.left = root.left;
            return node;
        }
    }
}
